package _interview100;

import _object.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 98. 验证二叉搜索树
 */
public class No98 {
    private Queue<Integer> queue;

    public boolean isValidBST(TreeNode root) {
        queue = new ArrayDeque<>();
        dfs(root);
        int preVal = queue.poll();
        while (!queue.isEmpty()) {
            Integer curVal = queue.poll();
            if (preVal >= curVal) return false;
            preVal = curVal;
        }
        return true;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        queue.add(node.val);
        dfs(node.right);
    }


    /*
      二、3种遍历方式
     */
    public boolean isValidBST2(TreeNode root) {
        return inorderTraversal(root);
    }

    /**
     * 前序遍历
     */
    public boolean preorderTraversal(TreeNode root, long left, long right) {
        if (root == null) {
            return true;
        }
        int val = root.val;
        if (val > left && val < right) {
            return preorderTraversal(root.left, left, val) && preorderTraversal(root.right, val, right);
        } else {
            return false;
        }
    }

    long pre = Long.MIN_VALUE;

    /**
     * 中序遍历
     */
    public boolean inorderTraversal(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (inorderTraversal(root.left) && root.val > pre) {
            pre = root.val;
        } else {
            return false;
        }
        return inorderTraversal(root.right);
    }

    /**
     * 后序遍历
     */
    private long[] postorderTraversal(TreeNode node) {
        if (node == null)
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        long[] left = postorderTraversal(node.left);
        long[] right = postorderTraversal(node.right);
        long x = node.val;
        // 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
        if (x <= left[1] || x >= right[0])
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        return new long[]{Math.min(left[0], x), Math.max(right[1], x)};
    }
}
